package leetcode.alg.demo;

import org.omg.PortableInterceptor.SYSTEM_EXCEPTION;
import sun.reflect.generics.tree.Tree;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 请实现两个函数，分别用来序列化和反序列化二叉树。
 *
 * 序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，
 * 同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。
 *
 * 请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，
 * 你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
 *
 * 示例: 
 *
 * 你可以将以下二叉树：
 *
 *     1
 *    / \
 *   2   3
 *      / \
 *     4   5
 *
 * 序列化为 "[1,2,3,null,null,4,5]"
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/xu-lie-hua-er-cha-shu-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Serialization_binary_tree {
    static TreeNode root = new TreeNode(1);
    static {
        TreeNode node_2 = new TreeNode(2);
        TreeNode node_3 = new TreeNode(3);
        TreeNode node_4 = new TreeNode(4);
        TreeNode node_5 = new TreeNode(5);
        root.left = node_2;
        root.right = node_3;
        node_3.left = node_4;
        node_3.right = node_5;
    }

    public static void main(String[] args){
        Serialization_binary_tree serialization_binary_tree = new Serialization_binary_tree();
        String str = serialization_binary_tree.serialize(root);
        System.out.println(str);
        TreeNode node = serialization_binary_tree.deserialize(str);
        System.out.println(node);
    }

    public String serialize(TreeNode node) {
        return serialize_detail(node, "");
    }

    //递归序列化二叉树
    public String serialize_detail(TreeNode node, String str){
        if(node == null){
            str = str + "null, ";
        }else{
            str = str + node.val + ", ";
            str = serialize_detail(node.left, str);
            str = serialize_detail(node.right, str);
        }
        return str;
    }

    public TreeNode deserialize(String data) {
        String[] str_arrays = data.split(",");
        List<String> lists = new ArrayList<>(Arrays.asList(str_arrays));
        return deserialize_detail(lists);
    }

    // 递归反序列化，先构建List，通过List构建二叉树
    public TreeNode deserialize_detail(List<String> lists){
        TreeNode treeNode = null;
        if(lists.size() != 0){
            if(lists.get(0).equals("null")){
                lists.remove(0);
                return null;
            }
            if(!lists.get(0).trim().equals("null") && !lists.get(0).trim().equals("")) {
                treeNode = new TreeNode(Integer.valueOf(lists.get(0).trim()));
            }
            lists.remove(0);
            if(treeNode != null){
                treeNode.left = deserialize_detail(lists);
                treeNode.right = deserialize_detail(lists);
            }
        }
        return treeNode;
    }

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x){
            val = x;
        }

        @Override
        public String toString() {
            return "TreeNode{" +
                    "val=" + val +
                    ", left=" + left +
                    ", right=" + right +
                    '}';
        }
    }
}
